#define _CRT_SECURE_NO_WARNINGS 1
int nextP[4][2] = { {1, 0},{-1, 0},{0, 1},{0, -1} };

class Solution {
public:
    void DFS(vector<vector<char>>& grid, vector<vector<int>>& book, int row, int col, int curX, int curY)
    {
        book[curX][curY] = 1;
        for (int i = 0; i < 4; i++)
        {
            int newX = curX + nextP[i][0];
            int newY = curY + nextP[i][1];
            if (newX < 0 || newX >= row || newY < 0 || newY >= col)
            {
                continue;
            }
            if (book[newX][newY] == 0 && grid[newX][newY] == '1')
            {
                DFS(grid, book, row, col, newX, newY);
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<int>> book(row, vector<int>(col, 0));
        int num = 0;
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (book[i][j] == 0 && grid[i][j] == '1')
                {
                    DFS(grid, book, row, col, i, j);
                    num++;
                }
            }
        }
        return num;
    }
};